/*
 * main.hpp
 * Author: Elias Capito, Yanick Candaux
 * PCM
 */

#ifndef SolverParallProf_HPP_
#define SolverParallProf_HPP_


#include "def.hpp"
#include "BoardInfos.hpp"
#include "HazardQueue.hpp"
#include "Hash.hpp"

#include <cstring>
#include <math.h>

#include <omp.h>

using namespace  std;

namespace pcm {

class SolverParallProf {
public:
	SolverParallProf();
	virtual ~SolverParallProf();
	
	/**
	 * Execute
	 * @param _boardInfos
	 * @param jump
	 * @param m_boardDiscovered
	 * @param m_boardToProcess
	 * @param boardToReuse
	 * @param iThreadQueue
	 * @param iThreadHash
	 */
	void executeMove(BoardInfos* _boardInfos,HoleJump & jump,Hash  *m_boardDiscovered,HazardQueue *m_boardToProcess,HazardQueue *boardToReuse,int iThreadQueue,int iThreadHash){

		BoardInfos* newBoardInfos;
		if((newBoardInfos = boardToReuse->deq(0))==NULL){
			newBoardInfos = new BoardInfos(_boardInfos);
		}else{
			newBoardInfos->updateBoardInfos(_boardInfos);
		}
		//ApplyMove on a new board
		newBoardInfos->setHole(jump.start(),false);
		newBoardInfos->setHole(jump.jump(),false);
		newBoardInfos->setHole(jump.end(),true);
		newBoardInfos->decrementNumberPeg();
#ifdef APPLYROTATESANDSYMMETRIES
		newBoardInfos->applyHolesPermutations();
#endif

		m_boardDiscovered->specificAddOrIncrement(newBoardInfos,m_boardToProcess,boardToReuse,iThreadQueue);
	}
		
	
	/**
	 * Solve a board
	 * @param board
	 * @param numberThreads
	 * @return
	 */
	LL solve(BoardInfos &board, int numberThreads){

		//Solutions of the board
		LL m_solutions= 0;

		//List for current block
		HazardQueue** currGlobalBoardToProcess = new HazardQueue*[numberThreads];
		HazardQueue** nextGlobalBoardToProcess = new HazardQueue*[numberThreads];

		//for last block line
		Hash  *globalBoardDiscovered= new Hash();
		//Hash  *globalBoardDiscovered= new Hash();

		int gameNumberH ;
		int numConseqLevelSeq1 ;
		int numBlocksToProceed ;
		int numLevelsToProceedAtEnd;

		//Board start
		BoardInfos* startBoard = new BoardInfos(&board);
		globalBoardDiscovered->add(startBoard);
		for(int i = 0;i<numberThreads;i++){
			currGlobalBoardToProcess[i] = new HazardQueue(numberThreads);
			nextGlobalBoardToProcess[i] = new HazardQueue(numberThreads);
		}
		currGlobalBoardToProcess[0]->enq(startBoard, 0);
		gameNumberH = BoardInfos::gameNumberHole();
		numConseqLevelSeq1 = ceil((numberThreads)/CONSEQUAL_LEVEL_EVERY_NUM_THREADS);
		numBlocksToProceed = ceil((gameNumberH-1)/((double)numConseqLevelSeq1));
		numLevelsToProceedAtEnd = (gameNumberH-1)%numConseqLevelSeq1;

		int threadWhoClearGlobalBoardDiscovered =  -1;

		#pragma omp parallel num_threads(numberThreads) shared(m_solutions,currGlobalBoardToProcess,nextGlobalBoardToProcess,globalBoardDiscovered,gameNumberH,numConseqLevelSeq1,numBlocksToProceed,numLevelsToProceedAtEnd)
		{
			//Thread index
			int iThread = omp_get_thread_num();
			LL localSolutions = 0;
			Hash  m_boardDiscovered; //for all lines block wihout last

			HazardQueue m_boardToReuse(1);
			BoardInfos* currBoardInfos;
			int lengthBTP;

			int numConseqLevelSeq = numConseqLevelSeq1;

			//For each block
			for (int itBlock = 0; itBlock < numBlocksToProceed ; itBlock++) {
				if (itBlock == numBlocksToProceed-1 && numLevelsToProceedAtEnd != 0) {
					numConseqLevelSeq = numLevelsToProceedAtEnd;
				}
				
				int nextList = iThread;

				//For each consequal level (depth to process )
				for (int level = 0; level < numConseqLevelSeq ; level++) {
					lengthBTP = currGlobalBoardToProcess[iThread]->size();
					for (int nbIt = 0; nbIt < lengthBTP; nbIt++) {

						currBoardInfos = currGlobalBoardToProcess[iThread]->deq(iThread);

						//Find moves
						if((currBoardInfos->numberPeg()+currBoardInfos->numberPeg()) > BoardInfos::gameNumberHole()){ //TODO: Looking for the better multiplication
							//Find empty hole
							for(int iHole=0;iHole<BoardInfos::gameNumberHole();iHole++){
								bool hole = currBoardInfos->hole(iHole);
								if(!hole){
									vector<HoleJump> jumps= BoardInfos::endlHoleJumps(iHole);
									for(size_t iJump=0;iJump<BoardInfos::endHoleJumpsSize(iHole);iJump++){
										//Is a correct move
										if(currBoardInfos->hole(jumps[iJump].start()) && currBoardInfos->hole(jumps[iJump].jump())){
											if (level == numConseqLevelSeq-1) {
												executeMove(currBoardInfos,jumps[iJump], globalBoardDiscovered, (nextGlobalBoardToProcess[nextList]),&m_boardToReuse,iThread,iThread);
												if(++nextList==numberThreads){
													nextList %=numberThreads;
												}
												if(numConseqLevelSeq>1){
													m_boardDiscovered.remove(currBoardInfos);
												}
											}else {
												//another line of a block, use the private hash and add on its list
												executeMove(currBoardInfos,jumps[iJump], &m_boardDiscovered, (currGlobalBoardToProcess[iThread]),&m_boardToReuse,iThread,0);
												m_boardDiscovered.remove(currBoardInfos);
											}
										}
									}
								}
							}
						}else{
							//Find oo. pattern
							for(int iHole=0;iHole<BoardInfos::gameNumberHole();iHole++){
								bool hole = currBoardInfos->hole(iHole);
								if(hole){
									vector<HoleJump> jumps= BoardInfos::startHoleJumps(iHole);
									for(size_t iJump=0;iJump<BoardInfos::startHoleJumpsSize(iHole);iJump++){
										//Is a correct move
										if( currBoardInfos->hole(jumps[iJump].jump()) && !currBoardInfos->hole(jumps[iJump].end())){
											if(currBoardInfos->numberPeg()>2){

												if (level == numConseqLevelSeq-1) {
													//last line of a block, use the shared hash and add on the list for the next block
													executeMove(currBoardInfos,jumps[iJump], globalBoardDiscovered, (nextGlobalBoardToProcess[nextList]),&m_boardToReuse,iThread,iThread);
													if(++nextList==numberThreads){
														nextList %=numberThreads;
													}
													if(numConseqLevelSeq>1){
														m_boardDiscovered.remove(currBoardInfos);
													}
												}else {
													//another line of a block, use the private hash and add on its list
													executeMove(currBoardInfos,jumps[iJump], &m_boardDiscovered, (currGlobalBoardToProcess[iThread]),&m_boardToReuse,iThread,0);
													m_boardDiscovered.remove(currBoardInfos);
												}
											}else{
												//Increment local solutions
												localSolutions+=currBoardInfos->numberJoin();
											}
										}
									}
								}
							}
						}
						m_boardToReuse.enq(currBoardInfos,0);
					}
				}

				//Wait before exchange queues
				#pragma omp barrier

				//Only master exchange
				#pragma omp master
				{
					HazardQueue** exchange = currGlobalBoardToProcess;
					currGlobalBoardToProcess = nextGlobalBoardToProcess;
					nextGlobalBoardToProcess = exchange;
				}
				//Wait for exchange
				#pragma omp barrier
			}



			//Clean local queue
			currGlobalBoardToProcess[iThread]->clear();
			nextGlobalBoardToProcess[iThread]->clear();

			while((currBoardInfos=m_boardToReuse.deq(0))!=NULL){
				delete currBoardInfos;
			}
			m_boardToReuse.clear();
			m_boardDiscovered.clear();

			//Update global solutions
			#pragma omp atomic
			m_solutions+= localSolutions;

			//Clean global hash
			if(bcas32(&threadWhoClearGlobalBoardDiscovered,-1,iThread)){
				globalBoardDiscovered->clear();
			}
		}
		delete [] currGlobalBoardToProcess;
		delete [] nextGlobalBoardToProcess;

		return m_solutions;
	}

};

} /* namespace pcm */
#endif /* SolverParallProf_H_ */





